#include <vector>

using namespace std;

// 利用二维前缀和信息迅速得到二维区域和
// 测试链接 : https://leetcode.cn/problems/range-sum-query-2d-immutable/

class NumMatrix 
{
private:
    vector<vector<int>> sum;

public:
    NumMatrix(vector<vector<int>>& matrix) 
    {
        int m = matrix.size(), n = matrix[0].size();
        sum.resize(m + 1, vector<int>(n + 1));
        for(int a = 1, c = 0; c < m; ++a, ++c)
        {
            for(int b = 1, d = 0; d < n; ++b, ++d)
            {
                sum[a][b] = matrix[c][d];
            }
        }

        for(int i = 1; i <= m; ++i)
        {
            for(int j = 1; j <= n; ++j)
            {
                sum[i][j] += sum[i][j - 1] + sum[i - 1][j] - sum[i - 1][j - 1];
            }
        }
    }
    
    int sumRegion(int a, int b, int c, int d) 
    {
        ++c;
        ++d;
        return sum[c][d] - sum[c][b] - sum[a][d] + sum[a][b];
    }
};